Programmable logic devices (PLDs) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. FIG. 1 is a simplified illustration of one type of PLD, the Field Programmable Gate Array (FPGA). An FPGA typically includes an array of configurable logic blocks (LBs 101a-101i) and programmable input/output blocks (I/Os 102a-102d). The LBs and I/O blocks are interconnected by a programmable interconnection array that includes a large number of interconnect lines 103 interconnected by programmable interconnect points (PIPs 104, shown as small circles in FIG. 1). PIPs are often coupled into groups (e.g., group 105) that implement multiplexer circuits selecting one of several interconnect lines to provide a signal to a destination interconnect line or logic block. Some FPGAs also include additional logic blocks with special purposes (not shown), e.g., DLLs, RAM, and so forth.
The interconnection array, LBs, I/O blocks, and other logic blocks are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the interconnection array and logic blocks are configured. The configuration data can be read from memory (e.g., from an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
FIG. 2 is a simplified illustration of another type of PLD called the Complex Programmable Logic Device, or CPLD. A CPLD includes two or more logic blocks (LBs 201a-201h) connected together and to input/output blocks (I/Os 202a-202f) by a programmable interconnection array (203). Each logic block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays (PLAs) and Programmable Array Logic (PAL) devices. The interconnection array includes many multiplexer circuits 205, each including several PIPs 204. In each multiplexer circuit 205, only one PIP 204 is enabled. The enabled PIP selects one of the many input signals provided to the interconnection array, and the selected input signal is provided as the output signal from the multiplexer circuit 205.
In some CPLDs, configuration data is stored on-chip in non-volatile memory. In other CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration sequence.
For all of these programmable logic devices (PLDs), the functionality of the device is controlled by data bits provided to the device for that purpose. The data bits can be stored in volatile memory (e.g., static RAM cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
Testing a large PLD can be a time-consuming process. A user design can utilize any of what can be millions of programmable elements on the PLD. Therefore, preferably every element on each PLD is thoroughly tested, including every programmable logic element and every interconnect line. This goal can be difficult to achieve using known technology, particularly the testing of all routing resources (e.g., interconnect lines, PIPs, routing multiplexers, and so forth) in a PLD.
Known routing software is designed to route nets between net terminals, typically from a known source terminal to a known load terminal. Known routing software is not designed to route through specific routing resources. Therefore, targeting a specific routing resource to be included in a test design can be very difficult.
According to known methods, to test routing resources in a PLD a set of test designs is created that collectively utilize all of the routing resources in the PLD (or as close to all as can reasonably be accomplished). The routing resources are included in the test designs in such a manner that if any routing resource in the PLD does not work correctly, then one of the test designs will fail to function properly and a testing failure will be reported.
Historically, a modified general product router has been used to test as many routing resources as possible in each design. To accomplish this goal, information is maintained in a database as to whether or not a routing resource has already been tested, and the router uses this information to help its expansion algorithm find untested routing resources. Most routers use general wave front expansion, which routes a single net or source/load pair at a time, and generally from the source to the load of the net. Resource costs are used to help guide the router in the right direction via the expansion algorithm used by the router. When previously untested resources are included in the design, a bonus is given for using these resources. When previously tested resources are included, a penalty is assessed.
However, this known method has its drawbacks. In particular, the process tends to build up penalty walls between net sources and untested resources, because everything close to the source is tested quickly.
Enhancements have been made to the process in an attempt to overcome this drawback. One such enhancement is to reduce the cost of a routing path's resources when an untested resource is found late in the process after penalty walls have been built. The rationale behind this approach is that if an untested resource is found late in the process, then there may be other untested resources in the same area. By reducing the cost of routing to the area, the probability of picking up more untested resources is increased.
When these known methods are used, untested routing resources are picked up quickly in the early stages of the routing process. However, the number of untested resources picked up by future passes drops off dramatically. In addition, the last few untested resources are frequently never picked up at all, because the expansion algorithm never locates them. These resources are often referred to as “hard to test” resources. To include these hard to test resources in test designs, test engineers frequently have to route them manually. This process can be difficult and time consuming. Additionally, the use of known methods can result in a set of test designs including a few designs that test a large number of resources, and a number of designs each of which tests very few additional resources.
In general, it is desirable to provide more efficient methods of generating test designs for PLDs that result in a smaller overall number of test designs.